#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL& x, LL& y)
{
	if (b == 0)
	{
		x = 1; y = 0;
		return a;
	}
	LL d, x1, y1;
	d = exgcd(b, a % b, x1, y1);
	x = y1, y = x1 - a / b * y1;
	return d;
}
int main()
{
	int t; cin >> t;
	while (t--)
	{
		LL a, b; cin >> a >> b;
		LL x, y, d;
		d = exgcd(a, b, x, y);
		if (d != 1) cout << -1 << endl;
		else cout << (x % b + b) % b << endl;
	}
	return 0;
}